package com.sinaapp.gavinzhang.jianzhioffer;

import org.junit.Test;

/**
 * 输入一个链表，输出该链表中倒数第k个结点。
 * Created by gavin on 15-9-4.
 */
public class FindKthToTail {

    @Test
    public void test()
    {
        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(2);
        listNode.next.next = new ListNode(3);
        listNode.next.next.next = new ListNode(4);

        System.out.println(FindKthToTail(listNode, 5));
    }
    static int i = -100;

    public static ListNode FindKthToTail(ListNode head,int k) {
        if (head == null) return null;
        ListNode node1 = head;
        ListNode node2 = head;
        int step = k;
        while (node2!=null && step != 0)
        {
            node2 = node2.next;
            step--;
        }
        if (step != 0)
            return null;
        while (node2 != null)
        {
            node2 = node2.next;
            node1 = node1.next;
        }

        return node1;



    }
    class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
}


